class Solution {

public:
    int numRollsToTarget(int n, int k, int target) {
        int dp[50][1010] = { 0 };
        dp[0][0] = 1;
        int mod = 1e9 + 7;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int x = 1; x <= k; x++) {
                    if (j >= x)dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % mod;
                }
            }
        }

        return dp[n][target];

    }
};